//Given a string s containing just the characters '(', ')', '{', '}', '[' and ']
//', determine if the input string is valid. 
//
// An input string is valid if: 
//
// 
// Open brackets must be closed by the same type of brackets. 
// Open brackets must be closed in the correct order. 
// 
//
// 
// Example 1: 
//
// 
//Input: s = "()"
//Output: true
// 
//
// Example 2: 
//
// 
//Input: s = "()[]{}"
//Output: true
// 
//
// Example 3: 
//
// 
//Input: s = "(]"
//Output: false
// 
//
// Example 4: 
//
// 
//Input: s = "([)]"
//Output: false
// 
//
// Example 5: 
//
// 
//Input: s = "{[]}"
//Output: true
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 10⁴ 
// s consists of parentheses only '()[]{}'. 
// 
// Related Topics String Stack 👍 9880 👎 385


package leetcode.editor.en;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class _20_ValidParentheses {
    public static void main(String[] args) {
        Solution solution = new _20_ValidParentheses().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValid(String s) {
            LinkedList<Character> stack = new LinkedList<>();
            stack.push('?');
            Map<Character, Character> map = new HashMap<>();
            map.put('(', ')');
            map.put('{', '}');
            map.put('[', ']');
            if (s.length()>0 && !map.containsKey(s.charAt(0))) {
                return false;
            }
            for (int i = 0; i < s.length(); i++) {
                if (map.containsKey(s.charAt(i))){
                    stack.push(s.charAt(i));
                }else if (map.getOrDefault(stack.pop(),'?')!= s.charAt(i)){
                    return false;
                }
            }
            return stack.size()==1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}